package com.shm.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 137. 只出现一次的数字 II
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
 *
 * 说明：
 *
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 *
 * 示例 1:
 *
 * 输入: [2,2,3,2]
 * 输出: 3
 * 示例 2:
 *
 * 输入: [0,1,0,1,0,1,99]
 * 输出: 99
 * @author SHM
 */
public class SingleNumberII {
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        long sum = 0;
        for (int num : nums) {
            set.add(num);
            sum+=(long)num;
        }
        long setSum = 0;
        for (Integer integer : set) {
            setSum+=(long)integer;
        }
        return (int)((3*setSum-sum)/2);
    }


    public int singleNumber_2(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i:nums){
            map.put(i,map.getOrDefault(i,0)+1);
        }
        Set<Integer> set = map.keySet();
        for(Integer i:set){
            if(map.get(i)==1){
                return i;
            }
        }
        return 0;
    }

    public int singleNumber_3(int[] nums) {
        int ones = 0, twos = 0;
        for (int x: nums) {
            // 之前出现过两次的，这次再出现就是出现了三次
            int threes = twos & x;

            // 之前出现过两次，这次没出现，是出现了两次。
            // 之前出现过一次的，这次再出现，也是出现了两次。
            twos = (twos & ~x) | (ones & x);

            // 统计记录出现了奇数次的，并从其中清除出现三次的。
            // 这样ones里面始终只会记录出现了一次的。
            ones = ones ^ x;
            ones &= ~threes;
        }
        return ones;
    }

    /**
     * 方法三：位运算符：NOT，AND 和 XOR
     * 思路
     *
     * 使用位运算符可以实现 \mathcal{O}(1)O(1) 的空间复杂度。
     *
     * \sim x \qquad \textrm{表示} \qquad \textrm{位运算 NOT}
     * ∼x表示位运算 NOT
     *
     * x \& y \qquad \textrm{表示} \qquad \textrm{位运算 AND}
     * x&y表示位运算 AND
     *
     * x \oplus y \qquad \textrm{表示} \qquad \textrm{位运算 XOR}
     * x⊕y表示位运算 XOR
     *
     * XOR
     *
     * 该运算符用于检测出现奇数次的位：1、3、5 等。
     *
     * 0 与任何数 XOR 结果为该数。
     *
     * 0 \oplus x = x
     * 0⊕x=x
     *
     * 两个相同的数 XOR 结果为 0。
     *
     * x \oplus x = 0
     * x⊕x=0
     *
     * 以此类推，只有某个位置的数字出现奇数次时，该位的掩码才不为 0。
     *
     *
     *
     * 因此，可以检测出出现一次的位和出现三次的位，但是要注意区分这两种情况。
     *
     * AND 和 NOT
     *
     * 为了区分出现一次的数字和出现三次的数字，使用两个位掩码：seen_once 和 seen_twice。
     *
     * 思路是：
     *
     * 仅当 seen_twice 未变时，改变 seen_once。
     *
     * 仅当 seen_once 未变时，改变seen_twice。
     *
     *
     *
     * 位掩码 seen_once 仅保留出现一次的数字，不保留出现三次的数字。
     * 复杂度分析
     *
     * 时间复杂度：\mathcal{O}(N)O(N)，遍历输入数组。
     *
     * 空间复杂度：\mathcal{O}(1)O(1)，不使用额外空间。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-ii-by-leetcode/
     * @param nums
     * @return
     */
    public int singleNumber_4(int[] nums) {
        int ones = 0, twos = 0;
        for (int num: nums) {
            ones = ~twos & (ones ^ num);
            twos = ~ones & (twos ^ num);
        }
        return ones;
    }
}
